package Offer020;

/**
 * 回文字符串中的个数
 * @author 23737
 * @time 2021.12.9
 */
public class Test {
    public static void main(String[] args) {

    }
}

/**
 * 动态规划
 */
class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        if(n == 0){
            return 0;
        }
        int res = 0;
        boolean[][] used = new boolean[n][n];

        for(int i=0; i<n; i++){
            for(int j=0; j<=i; j++){
                if(s.charAt(i) == s.charAt(j) && (i-j < 2 || used[j+1][i-1])){
                    used[j][i] = true;
                    res++;
                }
            }
        }
        return res;
    }
}
